package S_O_R_T;
public class QuickSort implements Sort {
       public int getNum(int a[],int s,int e){
           int num=0;
           int max=s;
           for(int i=s;i<e;i++){
               if(a[i]>=a[max])
                   max=i;                 
           }
           if(a[max]==a[s]){
               int temp=a[s];
               a[s]=a[e-1];
               a[e-1]=temp;
           }
           if(s+1==e)
               num=e;
           for(int i=s+1;i<e;i++){
               if(a[i]>=a[s]){
                   num=i;
               }
                   break;
           }
       return num;
       
}
       
       public void quicksort(int a[],int s,int e){
           if(s<e){
           //System.out.println("hello");
           int pivot=getNum(a,s,e);//下标为pivot的值必须>=下标为s的值
           int temp=0;
           temp=a[pivot];a[pivot]=a[s];a[s]=temp;//数组的数据交换
           //int temp2=pivot;pivot=s;s=temp2;//数组的数据交换
           int left=s+1;
           int right=e;
           int setNum=-1;//设置标志位
           if(left==right){
             if(a[s]>a[e]){
                 int tem=a[s];a[s]=a[e];a[e]=tem;
             }
           while(left<right){
               setNum=-1;
               if(a[left]>=a[pivot]&&a[right-1]<=a[pivot]&&setNum==-1){
                   int getNum=a[left];
                   a[left]=a[right];
                   a[right]=getNum;
                   left++;right--;
                   setNum=1;
                    //System.out.println("ss");
               }
              else if(a[left]>=a[pivot]&&a[right]>=a[pivot]&&setNum==-1){
                   right--;
                   setNum=1;
                   // System.out.println("ss");
               }
              else if(a[left]<=a[pivot]&&a[right]<=a[pivot]&&setNum==-1){
                   left++;
                   setNum=1;
                    //System.out.println("ss");
               }
             }
           }
                temp=a[pivot];a[pivot]=a[s];a[s]=temp;
                quicksort(a,s,pivot-1);
                quicksort(a,pivot+1,e);
                }
            } 
 }

